package com.yww.algorithm.sort;

import java.util.Arrays;

/**
 * @author yww
 * @description 计数排序（完善处理负数）
 * @since 2024/2/25 10:27
 */
public class CountingSort {
    public static void sort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            } else if (min > arr[i]) {
                min = arr[i];
            }
        }
        int[] counting = new int[max - min + 1];
        for (int num : arr) {
            counting[num - min]++;
        }
        int k = 0;
        for (int count = 0; count < counting.length; count++) {
            while (counting[count] > 0) {
                arr[k++] = count + min;
                counting[count]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {6, 5, 4, 3, 2, 1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
